/*
310. 最小高度树
https://leetcode.cn/problems/minimum-height-trees/description/
中等 2024/12/4
*/

const int MAX_NODES = 20010, MAX_EDGES = 40010, INF = 0x3f3f3f3f;

class Solution {
public:
    // 邻接表存储图
    int head[MAX_NODES], edges[MAX_EDGES], nextEdge[MAX_EDGES], edgeIndex;
    // d1: 最长路径长度, d2: 次长路径长度, up: 来自父节点的最长路径长度, parent: 记录最长路径的子节点
    int longestPath[MAX_NODES], secondLongestPath[MAX_NODES], upPath[MAX_NODES], parent[MAX_NODES];

    // 添加边到邻接表
    void addEdge(int a, int b) {
        edges[edgeIndex] = b;
        nextEdge[edgeIndex] = head[a];
        head[a] = edgeIndex++;
    }

    // 第一次DFS：计算每个节点的最长和次长路径长度
    int dfsLongest(int node, int from) {
        longestPath[node] = secondLongestPath[node] = 0;
        for (int i = head[node]; i != -1; i = nextEdge[i]) {
            int neighbor = edges[i];
            if (neighbor == from) continue;

            int pathLength = dfsLongest(neighbor, node) + 1;

            if (pathLength >= longestPath[node]) {
                secondLongestPath[node] = longestPath[node];
                longestPath[node] = pathLength;
                parent[node] = neighbor; // 记录最长路径指向的子节点
            } else if (pathLength > secondLongestPath[node]) {
                secondLongestPath[node] = pathLength;
            }
        }
        return longestPath[node];
    }

    // 第二次DFS：计算每个节点来自父节点的最长路径长度
    void dfsUp(int node, int from) {
        for (int i = head[node]; i != -1; i = nextEdge[i]) {
            int neighbor = edges[i];
            if (neighbor == from) continue;

            // 如果父节点的最长路径经过当前邻居，则使用次长路径，否则使用最长路径
            if (parent[node] != neighbor)
                upPath[neighbor] = max(upPath[node], longestPath[node]) + 1;
            else
                upPath[neighbor] = max(upPath[node], secondLongestPath[node]) + 1;

            dfsUp(neighbor, node);
        }
    }

    // 主函数：找到所有最小高度树的根节点
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        memset(head, -1, sizeof(head));
        memset(parent, -1, sizeof(parent));

        // 构建无向图的邻接表
        for (auto& edge : edges) {
            addEdge(edge[0], edge[1]);
            addEdge(edge[1], edge[0]);
        }

        // 从节点 0 开始进行第一次 DFS，计算每个节点的最长和次长路径长度
        dfsLongest(0, -1);

        // 从节点 0 开始进行第二次 DFS，计算每个节点来自父节点的最长路径长度
        dfsUp(0, -1);

        // 找到最小高度树的高度
        int minHeight = INF;
        for (int i = 0; i < n; ++i)
            minHeight = min(minHeight, max(longestPath[i], upPath[i]));

        // 收集所有满足条件的根节点
        vector<int> result;
        for (int i = 0; i < n; ++i)
            if (max(longestPath[i], upPath[i]) == minHeight)
                result.push_back(i);

        return result;
    }
};